public class Solution2044 {

    int max=Integer.MIN_VALUE;
    int count=0;

    public int countMaxOrSubsets(int[] nums) {
        dfs(0,nums,0);
        return count;
    }

    private void dfs(int k, int[] nums, int v) {
        if (k==nums.length){
            if (v>max){
                max=v;
                count=1;
            }else if (v==max){
                count++;
            }
            return;
        }
        dfs(k+1,nums,v|nums[k]);
        dfs(k+1,nums,v);
    }

    public static void main(String[] args) {
        System.out.println(new Solution2044().countMaxOrSubsets(new int[]{3,2,1,5}));
    }
}
